package offer.twoPointers;

/**
 * @author DengYuan2
 * @create 2021-02-20 20:35
 */
public class n_58_1 {
    public static void main(String[] args) {
        n_58_1 n = new n_58_1();
        String str = "nowcoder. a am I";
        String res = n.ReverseSentence2(str);
        System.out.println(res);
    }

    /**
     * 我的写法-虽然能实现，但有点乱，有时用了现成的str方法、有时又没用，应该不用的
     *
     * @param str
     * @return
     */
    public String ReverseSentence(String str) {
        if (str.length() == 0) {
            return str;
        }
        StringBuilder res = new StringBuilder();
        int l = 0;
        int r = 1;
        while (r <= str.length()) {
            if (r == str.length() || str.charAt(r) == ' ') {
                res.insert(0, str.substring(l, r));
                res.insert(0, ' ');
                l = r + 1;
                r = l + 1;
            } else {
                r++;
            }
        }
        res.deleteCharAt(0);
        return res.toString();
    }


    /**
     * 大神-思路；
     * 先翻转单个单词，再翻转整体
     * 另外：
     *     题目应该有一个隐含条件，就是不能用额外的空间。虽然 Java 的题目输入参数为 String
     *     类型，需要先创建一个字符数组使得空间复杂度为 O(N)，但是正确的参数类型应该和原书
     *     一样，为字符数组，并且只能使用该字符数组的空间。任何使用了额外空间的解法在面试时
     *     都会大打折扣，包括递归解法。
     *
     * @param str
     * @return
     */
    public String ReverseSentence2(String str) {
        char[] array = str.toCharArray();
        int l = 0;
        int r = l+1;
        while (r <= array.length) {
            if (r == array.length || array[r] == ' ') {
                //确定为一个单词，进行翻转
                reverse(array,l,r-1);
                l=r+1;
                r=l+1;
            }else {
                r++;
            }
        }
        //翻转全部
        reverse(array,0,array.length-1);
        return new String(array);
    }

    public void reverse(char[] array, int start, int end) {
        int left = start;
        int rifht = end;
        char tmp = 0;
        while (left < rifht) {
            tmp = array[left];
            array[left]=array[rifht];
            array[rifht]=tmp;
            left++;
            rifht--;
        }
    }
}
